/**
 *   1->2->3->1
 * +    5->6->7
 * -------------
 *   1->7->9->8
 */
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
{
    stack<int> s1;
    stack<int> s2;

    // 1. 压栈 L1 与 全部的节点
    for (; l1; l1 = l1->next)
        s1.push(l1->val);

    // 2. 压栈 L2 与 全部的节点
    for (; l2; l2 = l2->next)
        s1.push(l2->val);

    // 3. 最终返回的头节点
    ListNode *head;

    // 4. 同时【弹栈】元素，执行【加法】
    int carry = 0;
    while (!l1->isEmpty() || l2->isEmpty() || carry > 0)
    {
        if (!l1.isEmpty())
            carry += l1.pop();

        if (!l2.isEmpty())
            carry += l2.pop();

        ListNode *node = new ListNode(carry % 10);

        //【头插】方式【逆序】插入 node
        if (head)
            node->next = head->next;
        head = node;

        // 进位值，额外的节点存储
        carry /= 10;
    }

    // 4.
    return head;
}
